CS 5010: Problem Set 6

Out: Monday, October 20, 2014

Due: Monday, October 27, 2014 at 600pm local time.

The goal of this problem set is to give you practice using context arguments and invariants.

Remember that you must follow the design recipe, and write invariants (as WHERE clauses) whenever an argument represents context information.

You must use DrScheme's HtDP Intermediate Student Language with Lambda. Use list abstractions like filter, fold, and map whenever they are helpful. As before, you will be penalized for failing to use these when they are "obviously" applicable.

As usual, the rubric for grading is here. You should also refer to the more detailed guidelines here.

Starting with this problem set, we will not run automated testing on programs that do not pass the qualification tests.

1. Consider the outline of a piece of text, for example:

   1 The first section
   1.1 A subsection with no subsections
   1.2 Another subsection
   1.2.1 This is a subsection of 1.2
   1.2.2 This is another subsection of 1.2
   1.3 The last subsection of 1
   2 Another section
   2.1 More stuff
   2.2 Still more stuff
   

   We could represent such an outline as a list with one element per section or subsection. Each element of the list consists of two members: the section number, represented as a list of natural numbers, and a string.

   In this representation, the outline above would be represented as

   (((1) "The first section")
    ((1 1) "A subsection with no subsections")
    ((1 2) "Another subsection")
    ((1 2 1) "This is a subsection of 1.2")
    ((1 2 2) "This is another subsection of 1.2")
    ((1 3) "The last subsection of 1")
    ((2) "Another section")
    ((2 1) "More stuff")
    ((2 2) "Still more stuff"))
   

   (where we're using the "write" representation of lists).

   We'll call this the flat-list representation.

   A different representation would represent an outline as a list of sections, where a section contains a title, which is a string, and a list of subsections.

   Under this representation, the outline above would be represented as

   (("The first section"
     ("A subsection with no subsections")
     ("Another subsection"
       ("This is a subsection of 1.2")
       ("This is another subsection of 1.2"))
     ("The last subsection of 1"))
    ("Another section"
     ("More stuff")
     ("Still more stuff")))
   

   We'll call this the nested-list representation.

   Write a program called "outlines.rkt" that converts from the nested representation to the flat representation.

   Your program should use the following data definition:

   An Sexp is one of the following
   -- a String
   -- a NonNegInt
   -- a ListOfSexp
   
   A ListOfSexp is one of
   -- empty
   -- (cons Sexp ListOfSexp)
   

   First, write data definitions for NestedRep and FlatRep. Each of these will be subsets of Sexp. Be sure to include whatever invariants are applicable.

   An outline may be an empty document, in which case both the NestedRep and FlatRep would be the empty list.

   Then, provide the following functions:

   nested-rep? : Sexp -> Boolean
   GIVEN: an Sexp
   RETURNS: true iff it is the nested representation of some outline
   
   nested-to-flat : NestedRep -> FlatRep
   GIVEN: the representation of an outline as a nested list
   RETURNS: the flat representation of the outline
   

   You should switch to the "write" output representation in DrRacket (Choose Language > Show Details > Output Style > 'write') so that your output will look exactly like the ones above. With this output representation, your interaction should look like

   >  (nested-to-flat
       '(("The first section"
          ("A subsection with no subsections")
          ("Another subsection"
           ("This is a subsection of 1.2")
           ("This is another subsection of 1.2"))
          ("The last subsection of 1"))
         ("Another section"
          ("More stuff")
          ("Still more stuff"))))
   (((1) "The first section")
    ((1 1) "A subsection with no subsections")
    ((1 2) "Another subsection")
    ((1 2 1) "This is a subsection of 1.2")
    ((1 2 2) "This is another subsection of 1.2")
    ((1 3) "The last subsection of 1")
    ((2) "Another section")
    ((2 1) "More stuff")
    ((2 2) "Still more stuff"))
   > 
   

   There should be no structs in your input or output, just lists.

   As usual, before you turn in your solution, make sure it passes the tests in ps06-outlines-qualification.rkt. As before, download this file, save it in your set06 directory, and run it to qualify your program for grading. Be sure to commit this file to repository so we know that you've done this correctly.

   For what it's worth, my solution to this problem was 117 lines, not including tests, and in one recent semester the median reported time for this problem was 8.65 hours.

2. Consider the following definition of expressions:

   (define-struct sum-exp (exprs))
   (define-struct mult-exp (exprs))
   
   ;; An Expr is one of
   ;; -- Integer
   ;; -- (make-sum-exp NELOExpr)
   ;; -- (make-mult-exp NELOExpr)
   ;; Interpretation: a sum-exp represents a sum and a mult-exp
   ;; represents a multiplication. 
   
   ;; A LOExpr is one of
   ;; -- empty
   ;; -- (cons Expr LOExpr)
   
   ;; A NELOExpr is a non-empty LOExpr.
   

   Your task is to write a program called pretty.rkt that contains a pretty-printer for Exprs. More precisely, you are to provide a function

   expr-to-strings : Expr NonNegInt -> ListOfString
   GIVEN: An expression and a width
   RETURNS: A representation of the expression as a sequence of lines, with
   each line represented as a string of length not greater than the width.
   

   The rules for rendering the expression as a list of lines are as follows:

   1. The expression should be rendered on a single line if it fits within the specified width.
   2. Otherwise, render the subexpressions in a stacked fashion, that is, like

      	(+ expr1
      	   expr2
      	   ...
      	   exprN)
      

      and similarly for multiplication expressions.
   3. All subexpressions must fit within the space allotted minus the space for surrounding parentheses, if any. Apply the rendering algorithm recursively if needed.
   4. Note: there should be no spaces preceding a right parenthesis.
   5. The algorithm may determine that the given expression cannot fit within the allotted space. In this case, the algorithm should raise an appropriate error, using the function error.

   In addition, you must provide make-sum-exp, sum-exp-exprs, make-mult-exp, and mult-exp-exprs.

   In order to help you debug your program, we have provided in extras.rkt the function:

   display-strings! : ListOfString -> Void
   GIVEN: a list of strings
   EFFECT: displays the strings on separate lines
   RETURNS: no value
   
   Example:
   > (display-strings! "xyz" "abc") 
   xyz
   abc
   > 
   

   Be sure to download a fresh copy of extras.rkt containing this function.

   Here is a sample interaction:

   > hw-example-1
   (make-sum-exp (list 22 333 44))
   > (expr-to-strings hw-example-1 15)
   (list "(+ 22 333 44)")
   > (expr-to-strings hw-example-1 10)
   (list "(+ 22" "   333" "   44)")
   > 
   > (define (display-expr expr n)
       (display-strings! (expr-to-strings expr n)))
   > (display-expr hw-example-1 25)
   (+ 22 333 44)
   > (display-expr hw-example-1 10)
   (+ 22
      333
      44)
   > (display-expr hw-example-1 5)
   not enough room
   > hw-example-2
   (make-sum-exp
    (list
     (make-mult-exp (list 22 3333 44))
     (make-mult-exp
      (list
       (make-sum-exp (list 66 67 68))
       (make-mult-exp (list 42 43))))
     (make-mult-exp (list 77 88))))
   > (display-expr hw-example-2 100)
   (+ (* 22 3333 44) (* (+ 66 67 68) (* 42 43)) (* 77 88))
   > (display-expr hw-example-2 50)
   (+ (* 22 3333 44)
      (* (+ 66 67 68) (* 42 43))
      (* 77 88))
   > (display-expr hw-example-2 20)
   (+ (* 22 3333 44)
      (* (+ 66 67 68)
         (* 42 43))
      (* 77 88))
   > (display-expr hw-example-2 15)
   (+ (* 22
         3333
         44)
      (* (+ 66
            67
            68)
         (* 42
            43))
      (* 77 88))
   > 
   

   As usual, before you turn in your solution, make sure it passes the tests in ps06-pretty-qualification.rkt. As before, download this file, save it in your set06 directory, and run it to qualify your program for grading. Be sure to commit this file to repository so we know that you've done this correctly.

   Here are some hints on this problem.

   • display-strings! is useful for you to use in debugging your program, but we will be testing the lists of strings produced by expr-to-strngs. There is at most one list of strings that satisfies the requirements of the problem.
   • This problem requires careful analysis of the context. For example, when your program gets to the (* 42 43) in (expr-to-strings hw-example-2 20), what does it need to know about the context in order to produce this line? If there is more than one thing that it needs to know, you can introduce multiple context variables to keep track of them.
   • This problem requires careful wishlist management. To help you (and us) keep track of your organization, keep your wishlist as a tree. Please turn in some tree-like representation of the functions in your implementation, with expr-to-strings at the root, and an arrow from each function to the functions that it calls as helpers. (Recursions don't count). Show only the important functions. This needn't be fancy. You can use a tool like UMLet or PowerPoint if you like, but don't spend too much time on it. While we would like to have this as a PDF in the repository, it will suffice to bring a paper copy to the codewalk.
   • In the book, you will find two different data definitions for non-empty lists. One of these treats the first element of the list specially; the other treats the last one specially. I needed both in my solution; I suspect you will also need both. Be sure to write down both definitions and both templates, and be sure to indicate which one you are using when you use structural decomposition on a non-empty list.

   My solution to this problem took 175 lines, exclusive of tests, and the last time I gave this problem, the median reported time was 16.3 hours.